﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Genetic_algorithm
{
    class GenetiA
    {
       
        string[] Tosobniki; //np Tosobniki[0] to w tabeli TwartoscFunkcji[0] zawiera wartosc funkcjiDopasowania
        int[] TwartoscFunkcji;
        int SumaFunkcjiDopsaowania; //zawiera sume wszystkich osobnikow(funkcji dopasowania) z danego pokolenia np 1+3+5=9
        int iloscIteracji;  // zawiera informacje ile jest wszystkich pokolen
        int dlugosChromosonu; // zawiera informacje o dlugosci chromosomu
        int ilePrzezylo; //ile osobników przezylo po obliczeniu funkcji dopasowania

        public void losowaPopulacja()
        {
            string temp = "";
            string binary = "";
            Random t = new Random();
            for (int i = 0; i < Tosobniki.Length; i++)
            {


                temp = "";
                binary = "";
                for (int z = 0; z < dlugosChromosonu; z++)
                {
                    int a = t.Next(2);
                    temp = a.ToString();
                    binary += temp;
                }
                Tosobniki[i] = binary;
            }
        }
        int ktoryOsobnik(int x)
        { // zamienia wylosowana liczbe na numer osobnika np z przedziału <0,2) to osobnik 1
            //zwraca numer osobnika ktory jest wywołany do krzyzowania
            int a = 0;
            int b = 0;
            int i = 0;

            while (i < Tosobniki.Length )
            {
                b = a + TwartoscFunkcji[i];

                if (x >= a) if (b > x)
                        return i;
                a += TwartoscFunkcji[i];
                i++;


            }
            return -1;

        }
        public string NowyOsobnik(int IleRodzicow)
        {
            //wyrzukuje losowo rodzicow i tworzy nowgo osobnika
            string[] temp = new string[IleRodzicow];
            int[] numer = new int[IleRodzicow];
            Random x = new Random();
            int xx = 0;
            int i = 0;
            int wylosowanyNumer = 0;
            while (true)
            {
                
                xx = x.Next(SumaFunkcjiDopsaowania);
                if ((wylosowanyNumer = ktoryOsobnik(xx)) != -1)
                {
                    bool czyPotworka = false;
                    
                    for (int z = 0; z < i+1; z++)
                    {
                        if (numer[z] == wylosowanyNumer) czyPotworka = true;
                    }
                    numer[i] = wylosowanyNumer;
                    if (czyPotworka == false) i++;
                }
                if (i == IleRodzicow) break;

            }

            for (int b = 0; b < IleRodzicow; b++)

                temp[b] = Tosobniki[numer[b]];
 
 

            string osobnikNowy = "";
            int ile = dlugosChromosonu;
            Random t = new Random();

            i=0;
            int IleJuzJest = 0;
            while (true)
            {
                for (int b = 0; b < IleRodzicow; b++)
                {

                    int a = t.Next(ile) +1 + i;

                    osobnikNowy += temp[b].Substring(i, a - i);


                    ile = ile - (a - i);
                    i = a;
                    IleJuzJest = osobnikNowy.Length;
                    if (IleJuzJest == dlugosChromosonu) break;
                }
                if (IleJuzJest == dlugosChromosonu) break;
            }
            




            return osobnikNowy;
        }
        public  void  Krzyzowanie(int IleRodzicow)
        {
            //zwraca nowe pokolenie

            string[] TNowy = new string[Tosobniki.Length];
            for (int i = 0; i < Tosobniki.Length; i++)
                TNowy[i] = NowyOsobnik(IleRodzicow);
            
            Tosobniki = TNowy;

        }
        void mutacja(int MaxMutujeWiteracji)
        {

            // mutacja prawdopodobienstwo dla kazdego osobnika to 1 % gdy 
            //wylosuje ze nastepuje mutacja losuje czy mutuja dwa bity czy jeden a pozniej ktore to sa bity i zamienia na przeciwne
            // przy czym nr bita nie moze sie powtorzyc dla danego osobnika
            int n = 100;
            int ileMutowalo = 0;
            for (int i = 0; i < Tosobniki.Length; i++)
            {
                Random czyBedzieMutacja = new Random(i+20);
                int a = czyBedzieMutacja.Next(n);

                if (a == 0)
                {
                    Random ileBitow1czy2 = new Random(i+30);

                        Random ktoryBit = new Random(i+40);
                        int bit = ktoryBit.Next(dlugosChromosonu);
                        string osobnik = Tosobniki[i];
                        string nowy = osobnik.Substring(0, bit);
                        if (osobnik.Substring(bit, 1) == "0") nowy += "1";
                        else nowy += "0";
                        int ileOdjac = dlugosChromosonu - (bit + 1);
                        nowy += osobnik.Substring(bit + 1, ileOdjac);
                        Tosobniki[i] = nowy;
                        ileMutowalo++;
                  }
                if (ileMutowalo == MaxMutujeWiteracji) break;
            }
        }
        public int funkcjaDopasowania(string osobnikPorownywany, string wzorzec)
        {
            // oblicza funckeDpoasowania kazdego osobnika 

            // funkcja dopasowania będzie wynosić tyle, na ilu miejscach w osobniku danym i wzorcowym jest ta sama cyfra
            int ile = 0;
            for (int i = 0; i < wzorzec.Length; i++)
                if (osobnikPorownywany.Substring(i, 1) == wzorzec.Substring(i, 1))
                    ile++;
            SumaFunkcjiDopsaowania += ile;

            return ile;

        }
        int obliczenieFunkcjiOsobnika(string wzorzec)
        {






            // kazdemu osobnikowi oblica wartosc funkcji f i zapisuje do drugiej kolumny

                int wartosc = 0;
                for (int i = 0; i < Tosobniki.Length; i++)
                {
                    wartosc = funkcjaDopasowania(Tosobniki[i], wzorzec);
                    TwartoscFunkcji[i] = wartosc;
                    if (wartosc != 0) ilePrzezylo++;
                    if (wartosc == dlugosChromosonu) return i;

                }
            return -1;
        }


        public bool Rozwiazanie(string wzorzec, int ilePokolen, int iloscOsobnikow, int ileJestRodzicow, ref string wynik, int MaxMutujeWiteracji)
        {
            int najlepszy = -1;
            int liczbaNajlepszego = -1;
            Tosobniki = new string[iloscOsobnikow];
            TwartoscFunkcji = new int[iloscOsobnikow];
            this.dlugosChromosonu = wzorzec.Length;
            losowaPopulacja();
            for (int i = 0; i < ilePokolen; i++)
            {
                if (i != dlugosChromosonu - 1)
                {
                    mutacja(MaxMutujeWiteracji);

                    int nr = obliczenieFunkcjiOsobnika(wzorzec);

                    if (nr != -1)
                    {
                        wynik = Tosobniki[nr];
                        return true;
                    }

                    if (ilePrzezylo < 2) return false;

                    Krzyzowanie(ileJestRodzicow);


                    SumaFunkcjiDopsaowania = 0;


                    for (int j = 0; j < TwartoscFunkcji.Length; j++)
                    {
                        if (najlepszy < TwartoscFunkcji[j])
                        {
                            najlepszy = TwartoscFunkcji[j];
                            liczbaNajlepszego = j;
                        }



                    }

                    wynik = Tosobniki[liczbaNajlepszego];
                }

            }

         

            return true;
            
        }
    }
    
}
